#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    string isBalanced(string num){
        int sm[2]={0};
        for(int i=0;i<num.size();i++) sm[i&1]+=num[i]-'0';
        return sm[0]==sm[1] ? "true" : "false";
    }
};

class Solution2{
public:
    int minTimeToReach(vector<vector<int>>& moveTime){
        int n=moveTime.size(), m=moveTime[0].size();
        short dir[4][2]={0,1,1,0,-1,0,0,-1}; int dis[n][m];
        memset(dis, -1, sizeof(dis));
        priority_queue<array<int,3>,vector<array<int,3>>, greater<array<int,3>>> pq;
        pq.push({0,0,0});
        while(!pq.empty()){
            auto arr=pq.top(); pq.pop();
            int i=arr[1], j=arr[2];
            if(dis[i][j]>=0) continue;
            dis[i][j]=arr[0];
            for(int k=0;k<4;k++){
                int ii=i+dir[k][0], jj=j+dir[k][1];
                if(ii<0||jj<0||ii>=n||jj>=m||dis[ii][jj]>=0) continue;
                int val=max(moveTime[ii][jj]+1,dis[i][j]+1);
                pq.push({val,ii,jj});
            }
        }
        return dis[n-1][m-1];
    }
};

const int mod=1e9+7;
class Solution4{
public:
    int countBalancedPermutations(string num) {
        int n = num.size();
        int m = (n + 1) / 2;

        int sm = 0, cnt[10] = {0};
        for (char c : num) sm += c - '0', cnt[c - '0']++;
        if (sm & 1) return 0;
        sm /= 2;

        const int MOD = 1e9 + 7;
        auto update = [&](long long &a, long long b) {
            a = (a + b) % MOD;
        };

        long long C[n + 1][n + 1];
        memset(C, 0, sizeof(C));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) update(C[i][j], C[i - 1][j - 1] + C[i - 1][j]);
        }

        long long f[11][m + 1][sm + 1];
        memset(f, 0, sizeof(f));
        f[0][0][0] = 1;
        int now = 0;
        for (int i = 1; i <= 10; i++) {
            int x = i - 1;
            now += cnt[x];
            for (int j = 0; j <= m; j++) for (int k = 0; k <= sm; k++) {
                    int rem1 = m - j, rem2 = n - now - rem1;
                    if (rem1 < 0 || rem2 < 0) continue;
                    for (int jj = 0; jj <= cnt[x] && jj <= j && x * jj <= k; jj++) {
                        update(f[i][j][k], f[i - 1][j - jj][k - x * jj] * C[rem1 + jj][jj] % MOD * C[rem2 + cnt[x] - jj][cnt[x] - jj]);
                    }
                }
        }
        return f[10][m][sm];
    }
};

int main(){
    Solution s; cout<<s.isBalanced("1234")<<endl;
    vector<vector<int>> moveTime={{0,4},{4,5}};
    Solution2 s2; cout<<s2.minTimeToReach(moveTime)<<endl;
    Solution4 s4; cout<<s4.countBalancedPermutations("123")<<endl;
}